"""
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

"""


class Solution:
    def canPartition(self, nums) -> bool:  # [1,2,5]
        if len(nums) < 2 or sum(nums) % 2 != 0: return False
        half = sum(nums)//2
        dp = (half+1) * [False]
        dp[0] = True
        nums.sort()
        for j in nums:
            for i in range(half, j-1, -1):
                dp[i] |= dp[i-j]
        return dp[-1]

obj = Solution()
print(obj.canPartition([1, 2, 5]))



